package com.liyghting.datastructurealgorithm.linkedlist;

/**
 * 循环链表
 * 
 * @author LiYiGuang
 * @date 2018/11/7 10:21
 */
public class CycleLinkedList {

	private Node head = null;

	private Node tail = null;

	public Node findByValue(int value) {
		Node p = head;
		while (p != null && p.data != value) {
			p = p.next;
		}
		return p;
	}

	public Node findByIndex(int index) {
		Node p = head;
		int i = 0;
		while (p != null && i++ != index) {
			p = p.next;
		}
		return p;
	}

	public void insertToHead(int value) {
		Node newNode = new Node(value, null);
		insertToHead(newNode);
	}

	public void insertToHead(Node newNode) {
		if (head == null) {
			head = newNode;
			tail = head;
			head.next = tail;
			tail.next = head;
		} else {
			newNode.next = head;
			head = newNode;
			tail.next = head;
		}
	}

	public Node insertAfter(Node p, int value) {
		Node newNode = new Node(value, null);
		insertAfter(p, newNode);
		return newNode;
	}

	public void insertAfter(Node p, Node newNode) {
		if (p == null)
			return;
		if (p == tail) {
			tail = newNode;
		}
		newNode.next = p.next;
		p.next = newNode;

	}

	public void insertBefore(Node p, int value) {
		Node newNode = new Node(value, null);
		insertBefore(p, newNode);
	}

	public void insertBefore(Node p, Node newNode) {
		if (p == null)
			return;
		if (head == p) {
			insertToHead(newNode);
		}

		Node q = head;
		while (q != null && q.next != p) {
			q = q.next;
		}
		if (q == null)
			return;

		newNode.next = p;
		q.next = newNode;
	}

	public void deleteByNode(Node p) {
		if (head == null || p == null)
			return;
		if (p == head) {
			head = head.next;
			tail.next = head;
			return;
		}
		Node q = head;
		while (q != null && q.next != p) {
			q = q.next;
		}
		if (q == null)
			return;
		q.next = q.next.next;

	}

	public void deleteByValue(int value) {
		if (head == null)
			return;
		Node q = head;
		Node p = null;
		while (q != null && q.data != value) {
			p = q;
			q = q.next;
		}
		if (q == null)
			return;
		if (p == null) {
			head = head.next;
			tail.next = head;
		} else {
			p.next = p.next.next;
		}
		// 可重复删除指定value的代码

		if (head != null && head.data == value) {
			head = head.next;
			tail.next = head;
		}
		Node pNode = head;
		while (pNode != null && pNode.next != head) {
			if (pNode.next != null && pNode.next.data == value) {
				pNode.next = pNode.next.next;
				continue;
			}
			pNode = pNode.next;
		}

	}

	public void printAll() {
		Node p = head;
		System.out.print(p.data + " ");
		while (p != null && p.next != head) {
			System.out.print(p.next.data + " ");
			p = p.next;
		}
		System.out.println();
	}

	private static class Node {
		private int data;
		private Node next;

		public Node(int data, Node next) {
			this.data = data;
			this.next = next;
		}

		public int getData() {
			return data;
		}
	}

	public static void main(String[] args) {
		CycleLinkedList cl = new CycleLinkedList();
		Node node = new Node(0, null);
		cl.insertToHead(node);
		// cl.printAll();
		Node newNode = cl.insertAfter(node, 1);
		// cl.printAll();
		newNode = cl.insertAfter(newNode, 2);
		// cl.printAll();
		newNode = cl.insertAfter(newNode, 3);
		// cl.printAll();
		cl.insertBefore(newNode, 4);
		// cl.printAll();
		cl.insertToHead(5);
		cl.printAll();
		cl.deleteByValue(5);
		cl.printAll();
		cl.deleteByNode(newNode);
		cl.printAll();
		System.out.println(cl.findByValue(1).data);
		System.out.println(cl.findByIndex(0).data);
		System.out.println(cl.findByIndex(3).data);
		System.out.println("head data = " + cl.head.data);
		System.out.println("tail data = " + cl.tail.data);

	}
}
